import math
import sys
# sys.setrecursionlimit(10000)


def perfect_square_dp(n, perfect_square_dp_cache=[0]):
    if n < len(perfect_square_dp_cache):
        return perfect_square_dp_cache[n]
    minComp = n
    for i in range(1, math.floor(math.sqrt(n) + 1)):
        minComp = min(minComp, perfect_square_dp(n - i**2))
    result = minComp + 1
    if n == len(perfect_square_dp_cache):
        perfect_square_dp_cache.append(result)
    return result


with open('279.完全平方数.table.txt', 'w') as f1, open('279.完全平方数.array.txt', 'w') as f2:
    f1.write('switch(n) {\n')
    f2.write('vector<int> result({')
    for n in range(10001):
        count = perfect_square_dp(n)
        f1.write(f'case {n}: return {count};\n')
        f2.write(f'{count}, ')
        if n % 100 == 0:
            f2.write('\n')
    f1.write('defualt: return 0;}')
    f2.write('});')
